﻿//Copyright (C) Microsoft Corporation.  All rights reserved.

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using System.Linq.Expressions;
using System.Reflection;
using System.Reflection.Emit;
using System.Threading;

namespace System.Linq.Dynamic
{
  public static class DynamicQueryable
  {
    public static IQueryable<T> Where<T>(this IQueryable<T> source, string predicate, params object[] values)
    {
      return (IQueryable<T>)Where((IQueryable)source, predicate, values);
    }

    public static IQueryable Where(this IQueryable source, string predicate, params object[] values)
    {
      if (source == null) throw new ArgumentNullException("source");
      if (predicate == null) throw new ArgumentNullException("predicate");
      LambdaExpression lambda = DynamicExpression.ParseLambda(source.ElementType, typeof(bool), predicate, values);
      return source.Provider.CreateQuery(
          Expression.Call(
              typeof(Queryable), "Where",
              new Type[] { source.ElementType },
              source.Expression, Expression.Quote(lambda)));
    }

    public static IQueryable Select(this IQueryable source, string selector, params object[] values)
    {
      if (source == null) throw new ArgumentNullException("source");
      if (selector == null) throw new ArgumentNullException("selector");
      LambdaExpression lambda = DynamicExpression.ParseLambda(source.ElementType, null, selector, values);
      return source.Provider.CreateQuery(
          Expression.Call(
              typeof(Queryable), "Select",
              new Type[] { source.ElementType, lambda.Body.Type },
              source.Expression, Expression.Quote(lambda)));
    }

    public static IQueryable<T> OrderBy<T>(this IQueryable<T> source, string ordering, params object[] values)
    {
      return (IQueryable<T>)OrderBy((IQueryable)source, ordering, values);
    }

    public static IQueryable OrderBy(this IQueryable source, string ordering, params object[] values)
    {
      if (source == null) throw new ArgumentNullException("source");
      if (ordering == null) throw new ArgumentNullException("ordering");
      ParameterExpression[] parameters = new ParameterExpression[] {
                Expression.Parameter(source.ElementType, "") };
      ExpressionParser parser = new ExpressionParser(parameters, ordering, values);
      IEnumerable<DynamicOrdering> orderings = parser.ParseOrdering();
      Expression queryExpr = source.Expression;
      string methodAsc = "OrderBy";
      string methodDesc = "OrderByDescending";
      foreach (DynamicOrdering o in orderings)
      {
        queryExpr = Expression.Call(
            typeof(Queryable), o.Ascending ? methodAsc : methodDesc,
            new Type[] { source.ElementType, o.Selector.Type },
            queryExpr, Expression.Quote(Expression.Lambda(o.Selector, parameters)));
        methodAsc = "ThenBy";
        methodDesc = "ThenByDescending";
      }
      return source.Provider.CreateQuery(queryExpr);
    }

    public static IQueryable Take(this IQueryable source, int count)
    {
      if (source == null) throw new ArgumentNullException("source");
      return source.Provider.CreateQuery(
          Expression.Call(
              typeof(Queryable), "Take",
              new Type[] { source.ElementType },
              source.Expression, Expression.Constant(count)));
    }

    public static IQueryable Skip(this IQueryable source, int count)
    {
      if (source == null) throw new ArgumentNullException("source");
      return source.Provider.CreateQuery(
          Expression.Call(
              typeof(Queryable), "Skip",
              new Type[] { source.ElementType },
              source.Expression, Expression.Constant(count)));
    }

    public static IQueryable GroupBy(this IQueryable source, string keySelector, string elementSelector, params object[] values)
    {
      if (source == null) throw new ArgumentNullException("source");
      if (keySelector == null) throw new ArgumentNullException("keySelector");
      if (elementSelector == null) throw new ArgumentNullException("elementSelector");
      LambdaExpression keyLambda = DynamicExpression.ParseLambda(source.ElementType, null, keySelector, values);
      LambdaExpression elementLambda = DynamicExpression.ParseLambda(source.ElementType, null, elementSelector, values);
      return source.Provider.CreateQuery(
          Expression.Call(
              typeof(Queryable), "GroupBy",
              new Type[] { source.ElementType, keyLambda.Body.Type, elementLambda.Body.Type },
              source.Expression, Expression.Quote(keyLambda), Expression.Quote(elementLambda)));
    }

    public static bool Any(this IQueryable source)
    {
      if (source == null) throw new ArgumentNullException("source");
      return (bool)source.Provider.Execute(
          Expression.Call(
              typeof(Queryable), "Any",
              new Type[] { source.ElementType }, source.Expression));
    }

    public static int Count(this IQueryable source)
    {
      if (source == null) throw new ArgumentNullException("source");
      return (int)source.Provider.Execute(
          Expression.Call(
              typeof(Queryable), "Count",
              new Type[] { source.ElementType }, source.Expression));
    }
  }

  public abstract class DynamicClass
  {
    public override string ToString()
    {
      PropertyInfo[] props = this.GetType().GetProperties(BindingFlags.Instance | BindingFlags.Public);
      StringBuilder sb = new StringBuilder();
      sb.Append("{");
      for (int i = 0; i < props.Length; i++)
      {
        if (i > 0) sb.Append(", ");
        sb.Append(props[i].Name);
        sb.Append("=");
        sb.Append(props[i].GetValue(this, null));
      }
      sb.Append("}");
      return sb.ToString();
    }
  }

  public class DynamicProperty
  {
    string name;
    Type type;

    public DynamicProperty(string name, Type type)
    {
      if (name == null) throw new ArgumentNullException("name");
      if (type == null) throw new ArgumentNullException("type");
      this.name = name;
      this.type = type;
    }

    public string Name
    {
      get { return name; }
    }

    public Type Type
    {
      get { return type; }
    }
  }

  public static class DynamicExpression
  {
    public static Expression Parse(Type resultType, string expression, params object[] values)
    {
      ExpressionParser parser = new ExpressionParser(null, expression, values);
      return parser.Parse(resultType);
    }

    public static LambdaExpression ParseLambda(Type itType, Type resultType, string expression, params object[] values)
    {
      return ParseLambda(new ParameterExpression[] { Expression.Parameter(itType, "") }, resultType, expression, values);
    }

    public static LambdaExpression ParseLambda(ParameterExpression[] parameters, Type resultType, string expression, params object[] values)
    {
      ExpressionParser parser = new ExpressionParser(parameters, expression, values);
      return Expression.Lambda(parser.Parse(resultType), parameters);
    }

    public static Expression<Func<T, S>> ParseLambda<T, S>(string expression, params object[] values)
    {
      return (Expression<Func<T, S>>)ParseLambda(typeof(T), typeof(S), expression, values);
    }

    public static Type CreateClass(params DynamicProperty[] properties)
    {
      return ClassFactory.Instance.GetDynamicClass(properties);
    }

    public static Type CreateClass(IEnumerable<DynamicProperty> properties)
    {
      return ClassFactory.Instance.GetDynamicClass(properties);
    }
  }

  internal class DynamicOrdering
  {
    public Expression Selector;
    public bool Ascending;
  }

  internal class Signature : IEquatable<Signature>
  {
    public DynamicProperty[] properties;
    public int hashCode;

    public Signature(IEnumerable<DynamicProperty> properties)
    {
      this.properties = properties.ToArray();
      hashCode = 0;
      foreach (DynamicProperty p in properties)
      {
        hashCode ^= p.Name.GetHashCode() ^ p.Type.GetHashCode();
      }
    }

    public override int GetHashCode()
    {
      return hashCode;
    }

    public override bool Equals(object obj)
    {
      return obj is Signature ? Equals((Signature)obj) : false;
    }

    public bool Equals(Signature other)
    {
      if (properties.Length != other.properties.Length) return false;
      for (int i = 0; i < properties.Length; i++)
      {
        if (properties[i].Name != other.properties[i].Name ||
            properties[i].Type != other.properties[i].Type) return false;
      }
      return true;
    }
  }

  internal class ClassFactory
  {
    public static readonly ClassFactory Instance = new ClassFactory();

    static ClassFactory() { }  // Trigger lazy initialization of static fields

    ModuleBuilder module;
    Dictionary<Signature, Type> classes;
    int classCount;
    ReaderWriterLock rwLock;

    private ClassFactory()
    {
      AssemblyName name = new AssemblyName("DynamicClasses");
      AssemblyBuilder assembly = AppDomain.CurrentDomain.DefineDynamicAssembly(name, AssemblyBuilderAccess.Run);
#if ENABLE_LINQ_PARTIAL_TRUST
            new ReflectionPermission(PermissionState.Unrestricted).Assert();
#endif
      try
      {
        module = assembly.DefineDynamicModule("Module");
      }
      finally
      {
#if ENABLE_LINQ_PARTIAL_TRUST
                PermissionSet.RevertAssert();
#endif
      }
      classes = new Dictionary<Signature, Type>();
      rwLock = new ReaderWriterLock();
    }

    public Type GetDynamicClass(IEnumerable<DynamicProperty> properties)
    {
      rwLock.AcquireReaderLock(Timeout.Infinite);
      try
      {
        Signature signature = new Signature(properties);
        Type type;
        if (!classes.TryGetValue(signature, out type))
        {
          type = CreateDynamicClass(signature.properties);
          classes.Add(signature, type);
        }
        return type;
      }
      finally
      {
        rwLock.ReleaseReaderLock();
      }
    }

    Type CreateDynamicClass(DynamicProperty[] properties)
    {
      LockCookie cookie = rwLock.UpgradeToWriterLock(Timeout.Infinite);
      try
      {
        string typeName = "DynamicClass" + (classCount + 1);
#if ENABLE_LINQ_PARTIAL_TRUST
                new ReflectionPermission(PermissionState.Unrestricted).Assert();
#endif
        try
        {
          TypeBuilder tb = this.module.DefineType(typeName, TypeAttributes.Class |
              TypeAttributes.Public, typeof(DynamicClass));
          FieldInfo[] fields = GenerateProperties(tb, properties);
          GenerateEquals(tb, fields);
          GenerateGetHashCode(tb, fields);
          Type result = tb.CreateType();
          classCount++;
          return result;
        }
        finally
        {
#if ENABLE_LINQ_PARTIAL_TRUST
                    PermissionSet.RevertAssert();
#endif
        }
      }
      finally
      {
        rwLock.DowngradeFromWriterLock(ref cookie);
      }
    }

    FieldInfo[] GenerateProperties(TypeBuilder tb, DynamicProperty[] properties)
    {
      FieldInfo[] fields = new FieldBuilder[properties.Length];
      for (int i = 0; i < properties.Length; i++)
      {
        DynamicProperty dp = properties[i];
        FieldBuilder fb = tb.DefineField("_" + dp.Name, dp.Type, FieldAttributes.Private);
        PropertyBuilder pb = tb.DefineProperty(dp.Name, PropertyAttributes.HasDefault, dp.Type, null);
        MethodBuilder mbGet = tb.DefineMethod("get_" + dp.Name,
            MethodAttributes.Public | MethodAttributes.SpecialName | MethodAttributes.HideBySig,
            dp.Type, Type.EmptyTypes);
        ILGenerator genGet = mbGet.GetILGenerator();
        genGet.Emit(OpCodes.Ldarg_0);
        genGet.Emit(OpCodes.Ldfld, fb);
        genGet.Emit(OpCodes.Ret);
        MethodBuilder mbSet = tb.DefineMethod("set_" + dp.Name,
            MethodAttributes.Public | MethodAttributes.SpecialName | MethodAttributes.HideBySig,
            null, new Type[] { dp.Type });
        ILGenerator genSet = mbSet.GetILGenerator();
        genSet.Emit(OpCodes.Ldarg_0);
        genSet.Emit(OpCodes.Ldarg_1);
        genSet.Emit(OpCodes.Stfld, fb);
        genSet.Emit(OpCodes.Ret);
        pb.SetGetMethod(mbGet);
        pb.SetSetMethod(mbSet);
        fields[i] = fb;
      }
      return fields;
    }

    void GenerateEquals(TypeBuilder tb, FieldInfo[] fields)
    {
      MethodBuilder mb = tb.DefineMethod("Equals",
          MethodAttributes.Public | MethodAttributes.ReuseSlot |
          MethodAttributes.Virtual | MethodAttributes.HideBySig,
          typeof(bool), new Type[] { typeof(object) });
      ILGenerator gen = mb.GetILGenerator();
      LocalBuilder other = gen.DeclareLocal(tb);
      Label next = gen.DefineLabel();
      gen.Emit(OpCodes.Ldarg_1);
      gen.Emit(OpCodes.Isinst, tb);
      gen.Emit(OpCodes.Stloc, other);
      gen.Emit(OpCodes.Ldloc, other);
      gen.Emit(OpCodes.Brtrue_S, next);
      gen.Emit(OpCodes.Ldc_I4_0);
      gen.Emit(OpCodes.Ret);
      gen.MarkLabel(next);
      foreach (FieldInfo field in fields)
      {
        Type ft = field.FieldType;
        Type ct = typeof(EqualityComparer<>).MakeGenericType(ft);
        next = gen.DefineLabel();
        gen.EmitCall(OpCodes.Call, ct.GetMethod("get_Default"), null);
        gen.Emit(OpCodes.Ldarg_0);
        gen.Emit(OpCodes.Ldfld, field);
        gen.Emit(OpCodes.Ldloc, other);
        gen.Emit(OpCodes.Ldfld, field);
        gen.EmitCall(OpCodes.Callvirt, ct.GetMethod("Equals", new Type[] { ft, ft }), null);
        gen.Emit(OpCodes.Brtrue_S, next);
        gen.Emit(OpCodes.Ldc_I4_0);
        gen.Emit(OpCodes.Ret);
        gen.MarkLabel(next);
      }
      gen.Emit(OpCodes.Ldc_I4_1);
      gen.Emit(OpCodes.Ret);
    }

    void GenerateGetHashCode(TypeBuilder tb, FieldInfo[] fields)
    {
      MethodBuilder mb = tb.DefineMethod("GetHashCode",
          MethodAttributes.Public | MethodAttributes.ReuseSlot |
          MethodAttributes.Virtual | MethodAttributes.HideBySig,
          typeof(int), Type.EmptyTypes);
      ILGenerator gen = mb.GetILGenerator();
      gen.Emit(OpCodes.Ldc_I4_0);
      foreach (FieldInfo field in fields)
      {
        Type ft = field.FieldType;
        Type ct = typeof(EqualityComparer<>).MakeGenericType(ft);
        gen.EmitCall(OpCodes.Call, ct.GetMethod("get_Default"), null);
        gen.Emit(OpCodes.Ldarg_0);
        gen.Emit(OpCodes.Ldfld, field);
        gen.EmitCall(OpCodes.Callvirt, ct.GetMethod("GetHashCode", new Type[] { ft }), null);
        gen.Emit(OpCodes.Xor);
      }
      gen.Emit(OpCodes.Ret);
    }
  }

  public sealed class ParseException : Exception
  {
    int position;

    public ParseException(string message, int position)
      : base(message)
    {
      this.position = position;
    }

    public int Position
    {
      get { return position; }
    }

    public override string ToString()
    {
      return string.Format(Res.ParseExceptionFormat, Message, position);
    }
  }

  internal class ExpressionParser
  {
    struct Token
    {
      public TokenId id;
      public string text;
      public int pos;
    }

    enum TokenId
    {
      Unknown,
      End,
      Identifier,
      StringLiteral,
      IntegerLiteral,
      RealLiteral,
      Exclamation,
      Percent,
      Amphersand,
      OpenParen,
      CloseParen,
      Asterisk,
      Plus,
      Comma,
      Minus,
      Dot,
      Slash,
      Colon,
      LessThan,
      Equal,
      GreaterThan,
      Question,
      OpenBracket,
      CloseBracket,
      Bar,
      ExclamationEqual,
      DoubleAmphersand,
      LessThanEqual,
      LessGreater,
      DoubleEqual,
      GreaterThanEqual,
      DoubleBar
    }

    interface ILogicalSignatures
    {
      void F(bool x, bool y);
      void F(bool? x, bool? y);
    }

    interface IArithmeticSignatures
    {
      void F(int x, int y);
      void F(uint x, uint y);
      void F(long x, long y);
      void F(ulong x, ulong y);
      void F(float x, float y);
      void F(double x, double y);
      void F(decimal x, decimal y);
      void F(int? x, int? y);
      void F(uint? x, uint? y);
      void F(long? x, long? y);
      void F(ulong? x, ulong? y);
      void F(float? x, float? y);
      void F(double? x, double? y);
      void F(decimal? x, decimal? y);
    }

    interface IRelationalSignatures : IArithmeticSignatures
    {
      void F(string x, string y);
      void F(char x, char y);
      void F(DateTime x, DateTime y);
      void F(TimeSpan x, TimeSpan y);
      void F(char? x, char? y);
      void F(DateTime? x, DateTime? y);
      void F(TimeSpan? x, TimeSpan? y);
    }

    interface IEqualitySignatures : IRelationalSignatures
    {
      void F(bool x, bool y);
      void F(bool? x, bool? y);
    }

    interface IAddSignatures : IArithmeticSignatures
    {
      void F(DateTime x, TimeSpan y);
      void F(TimeSpan x, TimeSpan y);
      void F(DateTime? x, TimeSpan? y);
      void F(TimeSpan? x, TimeSpan? y);
    }

    interface ISubtractSignatures : IAddSignatures
    {
      void F(DateTime x, DateTime y);
      void F(DateTime? x, DateTime? y);
    }

    interface INegationSignatures
    {
      void F(int x);
      void F(long x);
      void F(float x);
      void F(double x);
      void F(decimal x);
      void F(int? x);
      void F(long? x);
      void F(float? x);
      void F(double? x);
      void F(decimal? x);
    }

    interface INotSignatures
    {
      void F(bool x);
      void F(bool? x);
    }

    interface IEnumerableSignatures
    {
      void Where(bool predicate);
      void Any();
      void Any(bool predicate);
      void All(bool predicate);
      void Count();
      void Count(bool predicate);
      void Min(object selector);
      void Max(object selector);
      void Sum(int selector);
      void Sum(int? selector);
      void Sum(long selector);
      void Sum(long? selector);
      void Sum(float selector);
      void Sum(float? selector);
      void Sum(double selector);
      void Sum(double? selector);
      void Sum(decimal selector);
      void Sum(decimal? selector);
      void Average(int selector);
      void Average(int? selector);
      void Average(long selector);
      void Average(long? selector);
      void Average(float selector);
      void Average(float? selector);
      void Average(double selector);
      void Average(double? selector);
      void Average(decimal selector);
      void Average(decimal? selector);
    }

    static readonly Type[] predefinedTypes = {
            typeof(Object),
            typeof(Boolean),
            typeof(Char),
            typeof(String),
            typeof(SByte),
            typeof(Byte),
            typeof(Int16),
            typeof(UInt16),
            typeof(Int32),
            typeof(UInt32),
            typeof(Int64),
            typeof(UInt64),
            typeof(Single),
            typeof(Double),
            typeof(Decimal),
            typeof(DateTime),
            typeof(TimeSpan),
            typeof(Guid),
            typeof(Math),
            typeof(Convert)
        };

    static readonly Expression trueLiteral = Expression.Constant(true);
    static readonly Expression falseLiteral = Expression.Constant(false);
    static readonly Expression nullLiteral = Expression.Constant(null);

    static readonly string keywordIt = "it";
    static readonly string keywordIif = "iif";
    static readonly string keywordNew = "new";

    static Dictionary<string, object> keywords;

    Dictionary<string, object> symbols;
    IDictionary<string, object> externals;
    Dictionary<Expression, string> literals;
    ParameterExpression it;
    string text;
    int textPos;
    int textLen;
    char ch;
    Token token;

    public ExpressionParser(ParameterExpression[] parameters, string expression, object[] values)
    {
      if (expression == null) throw new ArgumentNullException("expression");
      if (keywords == null) keywords = CreateKeywords();
      symbols = new Dictionary<string, object>(StringComparer.OrdinalIgnoreCase);
      literals = new Dictionary<Expression, string>();
      if (parameters != null) ProcessParameters(parameters);
      if (values != null) ProcessValues(values);
      text = expression;
      textLen = text.Length;
      SetTextPos(0);
      NextToken();
    }

    void ProcessParameters(ParameterExpression[] parameters)
    {
      foreach (ParameterExpression pe in parameters)
        if (!String.IsNullOrEmpty(pe.Name))
          AddSymbol(pe.Name, pe);
      if (parameters.Length == 1 && String.IsNullOrEmpty(parameters[0].Name))
        it = parameters[0];
    }

    void ProcessValues(object[] values)
    {
      for (int i = 0; i < values.Length; i++)
      {
        object value = values[i];
        if (i == values.Length - 1 && value is IDictionary<string, object>)
        {
          externals = (IDictionary<string, object>)value;
        }
        else
        {
          AddSymbol("@" + i.ToString(System.Globalization.CultureInfo.InvariantCulture), value);
        }
      }
    }

    void AddSymbol(string name, object value)
    {
      if (symbols.ContainsKey(name))
        throw ParseError(Res.DuplicateIdentifier, name);
      symbols.Add(name, value);
    }

    public Expression Parse(Type resultType)
    {
      int exprPos = token.pos;
      Expression expr = ParseExpression();
      if (resultType != null)
        if ((expr = PromoteExpression(expr, resultType, true)) == null)
          throw ParseError(exprPos, Res.ExpressionTypeMismatch, GetTypeName(resultType));
      ValidateToken(TokenId.End, Res.SyntaxError);
      return expr;
    }

#pragma warning disable 0219
    public IEnumerable<DynamicOrdering> ParseOrdering()
    {
      List<DynamicOrdering> orderings = new List<DynamicOrdering>();
      while (true)
      {
        Expression expr = ParseExpression();
        bool ascending = true;
        if (TokenIdentifierIs("asc") || TokenIdentifierIs("ascending"))
        {
          NextToken();
        }
        else if (TokenIdentifierIs("desc") || TokenIdentifierIs("descending"))
        {
          NextToken();
          ascending = false;
        }
        orderings.Add(new DynamicOrdering { Selector = expr, Ascending = ascending });
        if (token.id != TokenId.Comma) break;
        NextToken();
      }
      ValidateToken(TokenId.End, Res.SyntaxError);
      return orderings;
    }
#pragma warning restore 0219

    // ?: operator
    Expression ParseExpression()
    {
      int errorPos = token.pos;
      Expression expr = ParseLogicalOr();
      if (token.id == TokenId.Question)
      {
        NextToken();
        Expression expr1 = ParseExpression();
        ValidateToken(TokenId.Colon, Res.ColonExpected);
        NextToken();
        Expression expr2 = ParseExpression();
        expr = GenerateConditional(expr, expr1, expr2, errorPos);
      }
      return expr;
    }

    // ||, or operator
    Expression ParseLogicalOr()
    {
      Expression left = ParseLogicalAnd();
      while (token.id == TokenId.DoubleBar || TokenIdentifierIs("or"))
      {
        Token op = token;
        NextToken();
        Expression right = ParseLogicalAnd();
        CheckAndPromoteOperands(typeof(ILogicalSignatures), op.text, ref left, ref right, op.pos);
        left = Expression.OrElse(left, right);
      }
      return left;
    }

    // &&, and operator
    Expression ParseLogicalAnd()
    {
      Expression left = ParseComparison();
      while (token.id == TokenId.DoubleAmphersand || TokenIdentifierIs("and"))
      {
        Token op = token;
        NextToken();
        Expression right = ParseComparison();
        CheckAndPromoteOperands(typeof(ILogicalSignatures), op.text, ref left, ref right, op.pos);
        left = Expression.AndAlso(left, right);
      }
      return left;
    }

    // =, ==, !=, <>, >, >=, <, <= operators
    Expression ParseComparison()
    {
      Expression left = ParseAdditive();
      while (token.id == TokenId.Equal || token.id == TokenId.DoubleEqual ||
          token.id == TokenId.ExclamationEqual || token.id == TokenId.LessGreater ||
          token.id == TokenId.GreaterThan || token.id == TokenId.GreaterThanEqual ||
          token.id == TokenId.LessThan || token.id == TokenId.LessThanEqual)
      {
        Token op = token;
        NextToken();
        Expression right = ParseAdditive();
        bool isEquality = op.id == TokenId.Equal || op.id == TokenId.DoubleEqual ||
            op.id == TokenId.ExclamationEqual || op.id == TokenId.LessGreater;
        if (isEquality && !left.Type.IsValueType && !right.Type.IsValueType)
        {
          if (left.Type != right.Type)
          {
            if (left.Type.IsAssignableFrom(right.Type))
            {
              right = Expression.Convert(right, left.Type);
            }
            else if (right.Type.IsAssignableFrom(left.Type))
            {
              left = Expression.Convert(left, right.Type);
            }
            else
            {
              throw IncompatibleOperandsError(op.text, left, right, op.pos);
            }
          }
        }
        else if (IsEnumType(left.Type) || IsEnumType(right.Type))
        {
          if (left.Type != right.Type)
          {
            Expression e;
            if ((e = PromoteExpression(right, left.Type, true)) != null)
            {
              right = e;
            }
            else if ((e = PromoteExpression(left, right.Type, true)) != null)
            {
              left = e;
            }
            else
            {
              throw IncompatibleOperandsError(op.text, left, right, op.pos);
            }
          }
        }
        else
        {
          CheckAndPromoteOperands(isEquality ? typeof(IEqualitySignatures) : typeof(IRelationalSignatures),
              op.text, ref left, ref right, op.pos);
        }
        switch (op.id)
        {
          case TokenId.Equal:
          case TokenId.DoubleEqual:
            left = GenerateEqual(left, right);
            break;
          case TokenId.ExclamationEqual:
          case TokenId.LessGreater:
            left = GenerateNotEqual(left, right);
            break;
          case TokenId.GreaterThan:
            left = GenerateGreaterThan(left, right);
            break;
          case TokenId.GreaterThanEqual:
            left = GenerateGreaterThanEqual(left, right);
            break;
          case TokenId.LessThan:
            left = GenerateLessThan(left, right);
            break;
          case TokenId.LessThanEqual:
            left = GenerateLessThanEqual(left, right);
            break;
        }
      }
      return left;
    }

    // +, -, & operators
    Expression ParseAdditive()
    {
      Expression left = ParseMultiplicative();
      while (token.id == TokenId.Plus || token.id == TokenId.Minus ||
          token.id == TokenId.Amphersand)
      {
        Token op = token;
        NextToken();
        Expression right = ParseMultiplicative();
        switch (op.id)
        {
          case TokenId.Plus:
            if (left.Type == typeof(string) || right.Type == typeof(string))
              goto case TokenId.Amphersand;
            CheckAndPromoteOperands(typeof(IAddSignatures), op.text, ref left, ref right, op.pos);
            left = GenerateAdd(left, right);
            break;
          case TokenId.Minus:
            CheckAndPromoteOperands(typeof(ISubtractSignatures), op.text, ref left, ref right, op.pos);
            left = GenerateSubtract(left, right);
            break;
          case TokenId.Amphersand:
            left = GenerateStringConcat(left, right);
            break;
        }
      }
      return left;
    }

    // *, /, %, mod operators
    Expression ParseMultiplicative()
    {
      Expression left = ParseUnary();
      while (token.id == TokenId.Asterisk || token.id == TokenId.Slash ||
          token.id == TokenId.Percent || TokenIdentifierIs("mod"))
      {
        Token op = token;
        NextToken();
        Expression right = ParseUnary();
        CheckAndPromoteOperands(typeof(IArithmeticSignatures), op.text, ref left, ref right, op.pos);
        switch (op.id)
        {
          case TokenId.Asterisk:
            left = Expression.Multiply(left, right);
            break;
          case TokenId.Slash:
            left = Expression.Divide(left, right);
            break;
          case TokenId.Percent:
          case TokenId.Identifier:
            left = Expression.Modulo(left, right);
            break;
        }
      }
      return left;
    }

    // -, !, not unary operators
    Expression ParseUnary()
    {
      if (token.id == TokenId.Minus || token.id == TokenId.Exclamation ||
          TokenIdentifierIs("not"))
      {
        Token op = token;
        NextToken();
        if (op.id == TokenId.Minus && (token.id == TokenId.IntegerLiteral ||
            token.id == TokenId.RealLiteral))
        {
          token.text = "-" + token.text;
          token.pos = op.pos;
          return ParsePrimary();
        }
        Expression expr = ParseUnary();
        if (op.id == TokenId.Minus)
        {
          CheckAndPromoteOperand(typeof(INegationSignatures), op.text, ref expr, op.pos);
          expr = Expression.Negate(expr);
        }
        else
        {
          CheckAndPromoteOperand(typeof(INotSignatures), op.text, ref expr, op.pos);
          expr = Expression.Not(expr);
        }
        return expr;
      }
      return ParsePrimary();
    }

    Expression ParsePrimary()
    {
      Expression expr = ParsePrimaryStart();
      while (true)
      {
        if (token.id == TokenId.Dot)
        {
          NextToken();
          expr = ParseMemberAccess(null, expr);
        }
        else if (token.id == TokenId.OpenBracket)
        {
          expr = ParseElementAccess(expr);
        }
        else
        {
          break;
        }
      }
      return expr;
    }

    Expression ParsePrimaryStart()
    {
      switch (token.id)
      {
        case TokenId.Identifier:
          return ParseIdentifier();
        case TokenId.StringLiteral:
          return ParseStringLiteral();
        case TokenId.IntegerLiteral:
          return ParseIntegerLiteral();
        case TokenId.RealLiteral:
          return ParseRealLiteral();
        case TokenId.OpenParen:
          return ParseParenExpression();
        default:
          throw ParseError(Res.ExpressionExpected);
      }
    }

    Expression ParseStringLiteral()
    {
      ValidateToken(TokenId.StringLiteral);
      char quote = token.text[0];
      string s = token.text.Substring(1, token.text.Length - 2);
      int start = 0;
      while (true)
      {
        int i = s.IndexOf(quote, start);
        if (i < 0) break;
        s = s.Remove(i, 1);
        start = i + 1;
      }
      if (quote == '\'')
      {
        if (s.Length != 1)
          throw ParseError(Res.InvalidCharacterLiteral);
        NextToken();
        return CreateLiteral(s[0], s);
      }
      NextToken();
      return CreateLiteral(s, s);
    }

    Expression ParseIntegerLiteral()
    {
      ValidateToken(TokenId.IntegerLiteral);
      string text = token.text;
      if (text[0] != '-')
      {
        ulong value;
        if (!UInt64.TryParse(text, out value))
          throw ParseError(Res.InvalidIntegerLiteral, text);
        NextToken();
        if (value <= (ulong)Int32.MaxValue) return CreateLiteral((int)value, text);
        if (value <= (ulong)UInt32.MaxValue) return CreateLiteral((uint)value, text);
        if (value <= (ulong)Int64.MaxValue) return CreateLiteral((long)value, text);
        return CreateLiteral(value, text);
      }
      else
      {
        long value;
        if (!Int64.TryParse(text, out value))
          throw ParseError(Res.InvalidIntegerLiteral, text);
        NextToken();
        if (value >= Int32.MinValue && value <= Int32.MaxValue)
          return CreateLiteral((int)value, text);
        return CreateLiteral(value, text);
      }
    }

    Expression ParseRealLiteral()
    {
      ValidateToken(TokenId.RealLiteral);
      string text = token.text;
      object value = null;
      char last = text[text.Length - 1];
      if (last == 'F' || last == 'f')
      {
        float f;
        if (Single.TryParse(text.Substring(0, text.Length - 1), out f)) value = f;
      }
      else
      {
        double d;
        if (Double.TryParse(text, out d)) value = d;
      }
      if (value == null) throw ParseError(Res.InvalidRealLiteral, text);
      NextToken();
      return CreateLiteral(value, text);
    }

    Expression CreateLiteral(object value, string text)
    {
      ConstantExpression expr = Expression.Constant(value);
      literals.Add(expr, text);
      return expr;
    }

    Expression ParseParenExpression()
    {
      ValidateToken(TokenId.OpenParen, Res.OpenParenExpected);
      NextToken();
      Expression e = ParseExpression();
      ValidateToken(TokenId.CloseParen, Res.CloseParenOrOperatorExpected);
      NextToken();
      return e;
    }

    Expression ParseIdentifier()
    {
      ValidateToken(TokenId.Identifier);
      object value;
      if (keywords.TryGetValue(token.text, out value))
      {
        if (value is Type) return ParseTypeAccess((Type)value);
        if (value == (object)keywordIt) return ParseIt();
        if (value == (object)keywordIif) return ParseIif();
        if (value == (object)keywordNew) return ParseNew();
        NextToken();
        return (Expression)value;
      }
      if (symbols.TryGetValue(token.text, out value) ||
          externals != null && externals.TryGetValue(token.text, out value))
      {
        Expression expr = value as Expression;
        if (expr == null)
        {
          expr = Expression.Constant(value);
        }
        else
        {
          LambdaExpression lambda = expr as LambdaExpression;
          if (lambda != null) return ParseLambdaInvocation(lambda);
        }
        NextToken();
        return expr;
      }
      if (it != null) return ParseMemberAccess(null, it);
      throw ParseError(Res.UnknownIdentifier, token.text);
    }

    Expression ParseIt()
    {
      if (it == null)
        throw ParseError(Res.NoItInScope);
      NextToken();
      return it;
    }

    Expression ParseIif()
    {
      int errorPos = token.pos;
      NextToken();
      Expression[] args = ParseArgumentList();
      if (args.Length != 3)
        throw ParseError(errorPos, Res.IifRequiresThreeArgs);
      return GenerateConditional(args[0], args[1], args[2], errorPos);
    }

    Expression GenerateConditional(Expression test, Expression expr1, Expression expr2, int errorPos)
    {
      if (test.Type != typeof(bool))
        throw ParseError(errorPos, Res.FirstExprMustBeBool);
      if (expr1.Type != expr2.Type)
      {
        Expression expr1as2 = expr2 != nullLiteral ? PromoteExpression(expr1, expr2.Type, true) : null;
        Expression expr2as1 = expr1 != nullLiteral ? PromoteExpression(expr2, expr1.Type, true) : null;
        if (expr1as2 != null && expr2as1 == null)
        {
          expr1 = expr1as2;
        }
        else if (expr2as1 != null && expr1as2 == null)
        {
          expr2 = expr2as1;
        }
        else
        {
          string type1 = expr1 != nullLiteral ? expr1.Type.Name : "null";
          string type2 = expr2 != nullLiteral ? expr2.Type.Name : "null";
          if (expr1as2 != null && expr2as1 != null)
            throw ParseError(errorPos, Res.BothTypesConvertToOther, type1, type2);
          throw ParseError(errorPos, Res.NeitherTypeConvertsToOther, type1, type2);
        }
      }
      return Expression.Condition(test, expr1, expr2);
    }

    Expression ParseNew()
    {
      NextToken();
      ValidateToken(TokenId.OpenParen, Res.OpenParenExpected);
      NextToken();
      List<DynamicProperty> properties = new List<DynamicProperty>();
      List<Expression> expressions = new List<Expression>();
      while (true)
      {
        int exprPos = token.pos;
        Expression expr = ParseExpression();
        string propName;
        if (TokenIdentifierIs("as"))
        {
          NextToken();
          propName = GetIdentifier();
          NextToken();
        }
        else
        {
          MemberExpression me = expr as MemberExpression;
          if (me == null) throw ParseError(exprPos, Res.MissingAsClause);
          propName = me.Member.Name;
        }
        expressions.Add(expr);
        properties.Add(new DynamicProperty(propName, expr.Type));
        if (token.id != TokenId.Comma) break;
        NextToken();
      }
      ValidateToken(TokenId.CloseParen, Res.CloseParenOrCommaExpected);
      NextToken();
      Type type = DynamicExpression.CreateClass(properties);
      MemberBinding[] bindings = new MemberBinding[properties.Count];
      for (int i = 0; i < bindings.Length; i++)
        bindings[i] = Expression.Bind(type.GetProperty(properties[i].Name), expressions[i]);
      return Expression.MemberInit(Expression.New(type), bindings);
    }

    Expression ParseLambdaInvocation(LambdaExpression lambda)
    {
      int errorPos = token.pos;
      NextToken();
      Expression[] args = ParseArgumentList();
      MethodBase method;
      if (FindMethod(lambda.Type, "Invoke", false, args, out method) != 1)
        throw ParseError(errorPos, Res.ArgsIncompatibleWithLambda);
      return Expression.Invoke(lambda, args);
    }

    Expression ParseTypeAccess(Type type)
    {
      int errorPos = token.pos;
      NextToken();
      if (token.id == TokenId.Question)
      {
        if (!type.IsValueType || IsNullableType(type))
          throw ParseError(errorPos, Res.TypeHasNoNullableForm, GetTypeName(type));
        type = typeof(Nullable<>).MakeGenericType(type);
        NextToken();
      }
      if (token.id == TokenId.OpenParen)
      {
        Expression[] args = ParseArgumentList();
        MethodBase method;
        switch (FindBestMethod(type.GetConstructors(), args, out method))
        {
          case 0:
            if (args.Length == 1)
              return GenerateConversion(args[0], type, errorPos);
            throw ParseError(errorPos, Res.NoMatchingConstructor, GetTypeName(type));
          case 1:
            return Expression.New((ConstructorInfo)method, args);
          default:
            throw ParseError(errorPos, Res.AmbiguousConstructorInvocation, GetTypeName(type));
        }
      }
      ValidateToken(TokenId.Dot, Res.DotOrOpenParenExpected);
      NextToken();
      return ParseMemberAccess(type, null);
    }

    Expression GenerateConversion(Expression expr, Type type, int errorPos)
    {
      Type exprType = expr.Type;
      if (exprType == type) return expr;
      if (exprType.IsValueType && type.IsValueType)
      {
        if ((IsNullableType(exprType) || IsNullableType(type)) &&
            GetNonNullableType(exprType) == GetNonNullableType(type))
          return Expression.Convert(expr, type);
        if ((IsNumericType(exprType) || IsEnumType(exprType)) &&
            (IsNumericType(type)) || IsEnumType(type))
          return Expression.ConvertChecked(expr, type);
      }
      if (exprType.IsAssignableFrom(type) || type.IsAssignableFrom(exprType) ||
          exprType.IsInterface || type.IsInterface)
        return Expression.Convert(expr, type);
      throw ParseError(errorPos, Res.CannotConvertValue,
          GetTypeName(exprType), GetTypeName(type));
    }

    Expression ParseMemberAccess(Type type, Expression instance)
    {
      if (instance != null) type = instance.Type;
      int errorPos = token.pos;
      string id = GetIdentifier();
      NextToken();
      if (token.id == TokenId.OpenParen)
      {
        if (instance != null && type != typeof(string))
        {
          Type enumerableType = FindGenericType(typeof(IEnumerable<>), type);
          if (enumerableType != null)
          {
            Type elementType = enumerableType.GetGenericArguments()[0];
            return ParseAggregate(instance, elementType, id, errorPos);
          }
        }
        Expression[] args = ParseArgumentList();
        MethodBase mb;
        switch (FindMethod(type, id, instance == null, args, out mb))
        {
          case 0:
            throw ParseError(errorPos, Res.NoApplicableMethod,
                id, GetTypeName(type));
          case 1:
            MethodInfo method = (MethodInfo)mb;
            if (!IsPredefinedType(method.DeclaringType))
              throw ParseError(errorPos, Res.MethodsAreInaccessible, GetTypeName(method.DeclaringType));
            if (method.ReturnType == typeof(void))
              throw ParseError(errorPos, Res.MethodIsVoid,
                  id, GetTypeName(method.DeclaringType));
            return Expression.Call(instance, (MethodInfo)method, args);
          default:
            throw ParseError(errorPos, Res.AmbiguousMethodInvocation,
                id, GetTypeName(type));
        }
      }
      else
      {
        MemberInfo member = FindPropertyOrField(type, id, instance == null);
        if (member == null)
          throw ParseError(errorPos, Res.UnknownPropertyOrField,
              id, GetTypeName(type));
        return member is PropertyInfo ?
            Expression.Property(instance, (PropertyInfo)member) :
            Expression.Field(instance, (FieldInfo)member);
      }
    }

    static Type FindGenericType(Type generic, Type type)
    {
      while (type != null && type != typeof(object))
      {
        if (type.IsGenericType && type.GetGenericTypeDefinition() == generic) return type;
        if (generic.IsInterface)
        {
          foreach (Type intfType in type.GetInterfaces())
          {
            Type found = FindGenericType(generic, intfType);
            if (found != null) return found;
          }
        }
        type = type.BaseType;
      }
      return null;
    }

    Expression ParseAggregate(Expression instance, Type elementType, string methodName, int errorPos)
    {
      ParameterExpression outerIt = it;
      ParameterExpression innerIt = Expression.Parameter(elementType, "");
      it = innerIt;
      Expression[] args = ParseArgumentList();
      it = outerIt;
      MethodBase signature;
      if (FindMethod(typeof(IEnumerableSignatures), methodName, false, args, out signature) != 1)
        throw ParseError(errorPos, Res.NoApplicableAggregate, methodName);
      Type[] typeArgs;
      if (signature.Name == "Min" || signature.Name == "Max")
      {
        typeArgs = new Type[] { elementType, args[0].Type };
      }
      else
      {
        typeArgs = new Type[] { elementType };
      }
      if (args.Length == 0)
      {
        args = new Expression[] { instance };
      }
      else
      {
        args = new Expression[] { instance, Expression.Lambda(args[0], innerIt) };
      }
      return Expression.Call(typeof(Enumerable), signature.Name, typeArgs, args);
    }

    Expression[] ParseArgumentList()
    {
      ValidateToken(TokenId.OpenParen, Res.OpenParenExpected);
      NextToken();
      Expression[] args = token.id != TokenId.CloseParen ? ParseArguments() : new Expression[0];
      ValidateToken(TokenId.CloseParen, Res.CloseParenOrCommaExpected);
      NextToken();
      return args;
    }

    Expression[] ParseArguments()
    {
      List<Expression> argList = new List<Expression>();
      while (true)
      {
        argList.Add(ParseExpression());
        if (token.id != TokenId.Comma) break;
        NextToken();
      }
      return argList.ToArray();
    }

    Expression ParseElementAccess(Expression expr)
    {
      int errorPos = token.pos;
      ValidateToken(TokenId.OpenBracket, Res.OpenParenExpected);
      NextToken();
      Expression[] args = ParseArguments();
      ValidateToken(TokenId.CloseBracket, Res.CloseBracketOrCommaExpected);
      NextToken();
      if (expr.Type.IsArray)
      {
        if (expr.Type.GetArrayRank() != 1 || args.Length != 1)
          throw ParseError(errorPos, Res.CannotIndexMultiDimArray);
        Expression index = PromoteExpression(args[0], typeof(int), true);
        if (index == null)
          throw ParseError(errorPos, Res.InvalidIndex);
        return Expression.ArrayIndex(expr, index);
      }
      else
      {
        MethodBase mb;
        switch (FindIndexer(expr.Type, args, out mb))
        {
          case 0:
            throw ParseError(errorPos, Res.NoApplicableIndexer,
                GetTypeName(expr.Type));
          case 1:
            return Expression.Call(expr, (MethodInfo)mb, args);
          default:
            throw ParseError(errorPos, Res.AmbiguousIndexerInvocation,
                GetTypeName(expr.Type));
        }
      }
    }

    static bool IsPredefinedType(Type type)
    {
      foreach (Type t in predefinedTypes) if (t == type) return true;
      return false;
    }

    static bool IsNullableType(Type type)
    {
      return type.IsGenericType && type.GetGenericTypeDefinition() == typeof(Nullable<>);
    }

    static Type GetNonNullableType(Type type)
    {
      return IsNullableType(type) ? type.GetGenericArguments()[0] : type;
    }

    static string GetTypeName(Type type)
    {
      Type baseType = GetNonNullableType(type);
      string s = baseType.Name;
      if (type != baseType) s += '?';
      return s;
    }

    static bool IsNumericType(Type type)
    {
      return GetNumericTypeKind(type) != 0;
    }

    static bool IsSignedIntegralType(Type type)
    {
      return GetNumericTypeKind(type) == 2;
    }

    static bool IsUnsignedIntegralType(Type type)
    {
      return GetNumericTypeKind(type) == 3;
    }

    static int GetNumericTypeKind(Type type)
    {
      type = GetNonNullableType(type);
      if (type.IsEnum) return 0;
      switch (Type.GetTypeCode(type))
      {
        case TypeCode.Char:
        case TypeCode.Single:
        case TypeCode.Double:
        case TypeCode.Decimal:
          return 1;
        case TypeCode.SByte:
        case TypeCode.Int16:
        case TypeCode.Int32:
        case TypeCode.Int64:
          return 2;
        case TypeCode.Byte:
        case TypeCode.UInt16:
        case TypeCode.UInt32:
        case TypeCode.UInt64:
          return 3;
        default:
          return 0;
      }
    }

    static bool IsEnumType(Type type)
    {
      return GetNonNullableType(type).IsEnum;
    }

    void CheckAndPromoteOperand(Type signatures, string opName, ref Expression expr, int errorPos)
    {
      Expression[] args = new Expression[] { expr };
      MethodBase method;
      if (FindMethod(signatures, "F", false, args, out method) != 1)
        throw ParseError(errorPos, Res.IncompatibleOperand,
            opName, GetTypeName(args[0].Type));
      expr = args[0];
    }

    void CheckAndPromoteOperands(Type signatures, string opName, ref Expression left, ref Expression right, int errorPos)
    {
      Expression[] args = new Expression[] { left, right };
      MethodBase method;
      if (FindMethod(signatures, "F", false, args, out method) != 1)
        throw IncompatibleOperandsError(opName, left, right, errorPos);
      left = args[0];
      right = args[1];
    }

    Exception IncompatibleOperandsError(string opName, Expression left, Expression right, int pos)
    {
      return ParseError(pos, Res.IncompatibleOperands,
          opName, GetTypeName(left.Type), GetTypeName(right.Type));
    }

    MemberInfo FindPropertyOrField(Type type, string memberName, bool staticAccess)
    {
      BindingFlags flags = BindingFlags.Public | BindingFlags.DeclaredOnly |
          (staticAccess ? BindingFlags.Static : BindingFlags.Instance);
      foreach (Type t in SelfAndBaseTypes(type))
      {
        MemberInfo[] members = t.FindMembers(MemberTypes.Property | MemberTypes.Field,
            flags, Type.FilterNameIgnoreCase, memberName);
        if (members.Length != 0) return members[0];
      }
      return null;
    }

    int FindMethod(Type type, string methodName, bool staticAccess, Expression[] args, out MethodBase method)
    {
      BindingFlags flags = BindingFlags.Public | BindingFlags.DeclaredOnly |
          (staticAccess ? BindingFlags.Static : BindingFlags.Instance);
      foreach (Type t in SelfAndBaseTypes(type))
      {
        MemberInfo[] members = t.FindMembers(MemberTypes.Method,
            flags, Type.FilterNameIgnoreCase, methodName);
        int count = FindBestMethod(members.Cast<MethodBase>(), args, out method);
        if (count != 0) return count;
      }
      method = null;
      return 0;
    }

    int FindIndexer(Type type, Expression[] args, out MethodBase method)
    {
      foreach (Type t in SelfAndBaseTypes(type))
      {
        MemberInfo[] members = t.GetDefaultMembers();
        if (members.Length != 0)
        {
          IEnumerable<MethodBase> methods = members.
              OfType<PropertyInfo>().
              Select(p => (MethodBase)p.GetGetMethod()).
              Where(m => m != null);
          int count = FindBestMethod(methods, args, out method);
          if (count != 0) return count;
        }
      }
      method = null;
      return 0;
    }

    static IEnumerable<Type> SelfAndBaseTypes(Type type)
    {
      if (type.IsInterface)
      {
        List<Type> types = new List<Type>();
        AddInterface(types, type);
        return types;
      }
      return SelfAndBaseClasses(type);
    }

    static IEnumerable<Type> SelfAndBaseClasses(Type type)
    {
      while (type != null)
      {
        yield return type;
        type = type.BaseType;
      }
    }

    static void AddInterface(List<Type> types, Type type)
    {
      if (!types.Contains(type))
      {
        types.Add(type);
        foreach (Type t in type.GetInterfaces()) AddInterface(types, t);
      }
    }

    class MethodData
    {
      public MethodBase MethodBase;
      public ParameterInfo[] Parameters;
      public Expression[] Args;
    }

    int FindBestMethod(IEnumerable<MethodBase> methods, Expression[] args, out MethodBase method)
    {
      MethodData[] applicable = methods.
          Select(m => new MethodData { MethodBase = m, Parameters = m.GetParameters() }).
          Where(m => IsApplicable(m, args)).
          ToArray();
      if (applicable.Length > 1)
      {
        applicable = applicable.
            Where(m => applicable.All(n => m == n || IsBetterThan(args, m, n))).
            ToArray();
      }
      if (applicable.Length == 1)
      {
        MethodData md = applicable[0];
        for (int i = 0; i < args.Length; i++) args[i] = md.Args[i];
        method = md.MethodBase;
      }
      else
      {
        method = null;
      }
      return applicable.Length;
    }

    bool IsApplicable(MethodData method, Expression[] args)
    {
      if (method.Parameters.Length != args.Length) return false;
      Expression[] promotedArgs = new Expression[args.Length];
      for (int i = 0; i < args.Length; i++)
      {
        ParameterInfo pi = method.Parameters[i];
        if (pi.IsOut) return false;
        Expression promoted = PromoteExpression(args[i], pi.ParameterType, false);
        if (promoted == null) return false;
        promotedArgs[i] = promoted;
      }
      method.Args = promotedArgs;
      return true;
    }

    Expression PromoteExpression(Expression expr, Type type, bool exact)
    {
      if (expr.Type == type) return expr;
      if (expr is ConstantExpression)
      {
        ConstantExpression ce = (ConstantExpression)expr;
        if (ce == nullLiteral)
        {
          if (!type.IsValueType || IsNullableType(type))
            return Expression.Constant(null, type);
        }
        else
        {
          string text;
          if (literals.TryGetValue(ce, out text))
          {
            Type target = GetNonNullableType(type);
            Object value = null;
            switch (Type.GetTypeCode(ce.Type))
            {
              case TypeCode.Int32:
              case TypeCode.UInt32:
              case TypeCode.Int64:
              case TypeCode.UInt64:
                value = ParseNumber(text, target);
                break;
              case TypeCode.Double:
                if (target == typeof(decimal)) value = ParseNumber(text, target);
                break;
              case TypeCode.String:
                value = ParseEnum(text, target);
                break;
            }
            if (value != null)
              return Expression.Constant(value, type);
          }
        }
      }
      if (IsCompatibleWith(expr.Type, type))
      {
        if (type.IsValueType || exact) return Expression.Convert(expr, type);
        return expr;
      }
      return null;
    }

    static object ParseNumber(string text, Type type)
    {
      switch (Type.GetTypeCode(GetNonNullableType(type)))
      {
        case TypeCode.SByte:
          sbyte sb;
          if (sbyte.TryParse(text, out sb)) return sb;
          break;
        case TypeCode.Byte:
          byte b;
          if (byte.TryParse(text, out b)) return b;
          break;
        case TypeCode.Int16:
          short s;
          if (short.TryParse(text, out s)) return s;
          break;
        case TypeCode.UInt16:
          ushort us;
          if (ushort.TryParse(text, out us)) return us;
          break;
        case TypeCode.Int32:
          int i;
          if (int.TryParse(text, out i)) return i;
          break;
        case TypeCode.UInt32:
          uint ui;
          if (uint.TryParse(text, out ui)) return ui;
          break;
        case TypeCode.Int64:
          long l;
          if (long.TryParse(text, out l)) return l;
          break;
        case TypeCode.UInt64:
          ulong ul;
          if (ulong.TryParse(text, out ul)) return ul;
          break;
        case TypeCode.Single:
          float f;
          if (float.TryParse(text, out f)) return f;
          break;
        case TypeCode.Double:
          double d;
          if (double.TryParse(text, out d)) return d;
          break;
        case TypeCode.Decimal:
          decimal e;
          if (decimal.TryParse(text, out e)) return e;
          break;
      }
      return null;
    }

    static object ParseEnum(string name, Type type)
    {
      if (type.IsEnum)
      {
        MemberInfo[] memberInfos = type.FindMembers(MemberTypes.Field,
            BindingFlags.Public | BindingFlags.DeclaredOnly | BindingFlags.Static,
            Type.FilterNameIgnoreCase, name);
        if (memberInfos.Length != 0) return ((FieldInfo)memberInfos[0]).GetValue(null);
      }
      return null;
    }

    static bool IsCompatibleWith(Type source, Type target)
    {
      if (source == target) return true;
      if (!target.IsValueType) return target.IsAssignableFrom(source);
      Type st = GetNonNullableType(source);
      Type tt = GetNonNullableType(target);
      if (st != source && tt == target) return false;
      TypeCode sc = st.IsEnum ? TypeCode.Object : Type.GetTypeCode(st);
      TypeCode tc = tt.IsEnum ? TypeCode.Object : Type.GetTypeCode(tt);
      switch (sc)
      {
        case TypeCode.SByte:
          switch (tc)
          {
            case TypeCode.SByte:
            case TypeCode.Int16:
            case TypeCode.Int32:
            case TypeCode.Int64:
            case TypeCode.Single:
            case TypeCode.Double:
            case TypeCode.Decimal:
              return true;
          }
          break;
        case TypeCode.Byte:
          switch (tc)
          {
            case TypeCode.Byte:
            case TypeCode.Int16:
            case TypeCode.UInt16:
            case TypeCode.Int32:
            case TypeCode.UInt32:
            case TypeCode.Int64:
            case TypeCode.UInt64:
            case TypeCode.Single:
            case TypeCode.Double:
            case TypeCode.Decimal:
              return true;
          }
          break;
        case TypeCode.Int16:
          switch (tc)
          {
            case TypeCode.Int16:
            case TypeCode.Int32:
            case TypeCode.Int64:
            case TypeCode.Single:
            case TypeCode.Double:
            case TypeCode.Decimal:
              return true;
          }
          break;
        case TypeCode.UInt16:
          switch (tc)
          {
            case TypeCode.UInt16:
            case TypeCode.Int32:
            case TypeCode.UInt32:
            case TypeCode.Int64:
            case TypeCode.UInt64:
            case TypeCode.Single:
            case TypeCode.Double:
            case TypeCode.Decimal:
              return true;
          }
          break;
        case TypeCode.Int32:
          switch (tc)
          {
            case TypeCode.Int32:
            case TypeCode.Int64:
            case TypeCode.Single:
            case TypeCode.Double:
            case TypeCode.Decimal:
              return true;
          }
          break;
        case TypeCode.UInt32:
          switch (tc)
          {
            case TypeCode.UInt32:
            case TypeCode.Int64:
            case TypeCode.UInt64:
            case TypeCode.Single:
            case TypeCode.Double:
            case TypeCode.Decimal:
              return true;
          }
          break;
        case TypeCode.Int64:
          switch (tc)
          {
            case TypeCode.Int64:
            case TypeCode.Single:
            case TypeCode.Double:
            case TypeCode.Decimal:
              return true;
          }
          break;
        case TypeCode.UInt64:
          switch (tc)
          {
            case TypeCode.UInt64:
            case TypeCode.Single:
            case TypeCode.Double:
            case TypeCode.Decimal:
              return true;
          }
          break;
        case TypeCode.Single:
          switch (tc)
          {
            case TypeCode.Single:
            case TypeCode.Double:
              return true;
          }
          break;
        default:
          if (st == tt) return true;
          break;
      }
      return false;
    }

    static bool IsBetterThan(Expression[] args, MethodData m1, MethodData m2)
    {
      bool better = false;
      for (int i = 0; i < args.Length; i++)
      {
        int c = CompareConversions(args[i].Type,
            m1.Parameters[i].ParameterType,
            m2.Parameters[i].ParameterType);
        if (c < 0) return false;
        if (c > 0) better = true;
      }
      return better;
    }

    // Return 1 if s -> t1 is a better conversion than s -> t2
    // Return -1 if s -> t2 is a better conversion than s -> t1
    // Return 0 if neither conversion is better
    static int CompareConversions(Type s, Type t1, Type t2)
    {
      if (t1 == t2) return 0;
      if (s == t1) return 1;
      if (s == t2) return -1;
      bool t1t2 = IsCompatibleWith(t1, t2);
      bool t2t1 = IsCompatibleWith(t2, t1);
      if (t1t2 && !t2t1) return 1;
      if (t2t1 && !t1t2) return -1;
      if (IsSignedIntegralType(t1) && IsUnsignedIntegralType(t2)) return 1;
      if (IsSignedIntegralType(t2) && IsUnsignedIntegralType(t1)) return -1;
      return 0;
    }

    Expression GenerateEqual(Expression left, Expression right)
    {
      return Expression.Equal(left, right);
    }

    Expression GenerateNotEqual(Expression left, Expression right)
    {
      return Expression.NotEqual(left, right);
    }

    Expression GenerateGreaterThan(Expression left, Expression right)
    {
      if (left.Type == typeof(string))
      {
        return Expression.GreaterThan(
            GenerateStaticMethodCall("Compare", left, right),
            Expression.Constant(0)
        );
      }
      return Expression.GreaterThan(left, right);
    }

    Expression GenerateGreaterThanEqual(Expression left, Expression right)
    {
      if (left.Type == typeof(string))
      {
        return Expression.GreaterThanOrEqual(
            GenerateStaticMethodCall("Compare", left, right),
            Expression.Constant(0)
        );
      }
      return Expression.GreaterThanOrEqual(left, right);
    }

    Expression GenerateLessThan(Expression left, Expression right)
    {
      if (left.Type == typeof(string))
      {
        return Expression.LessThan(
            GenerateStaticMethodCall("Compare", left, right),
            Expression.Constant(0)
        );
      }
      return Expression.LessThan(left, right);
    }

    Expression GenerateLessThanEqual(Expression left, Expression right)
    {
      if (left.Type == typeof(string))
      {
        return Expression.LessThanOrEqual(
            GenerateStaticMethodCall("Compare", left, right),
            Expression.Constant(0)
        );
      }
      return Expression.LessThanOrEqual(left, right);
    }

    Expression GenerateAdd(Expression left, Expression right)
    {
      if (left.Type == typeof(string) && right.Type == typeof(string))
      {
        return GenerateStaticMethodCall("Concat", left, right);
      }
      return Expression.Add(left, right);
    }

    Expression GenerateSubtract(Expression left, Expression right)
    {
      return Expression.Subtract(left, right);
    }

    Expression GenerateStringConcat(Expression left, Expression right)
    {
      return Expression.Call(
          null,
          typeof(string).GetMethod("Concat", new[] { typeof(object), typeof(object) }),
          new[] { left, right });
    }

    MethodInfo GetStaticMethod(string methodName, Expression left, Expression right)
    {
      return left.Type.GetMethod(methodName, new[] { left.Type, right.Type });
    }

    Expression GenerateStaticMethodCall(string methodName, Expression left, Expression right)
    {
      return Expression.Call(null, GetStaticMethod(methodName, left, right), new[] { left, right });
    }

    void SetTextPos(int pos)
    {
      textPos = pos;
      ch = textPos < textLen ? text[textPos] : '\0';
    }

    void NextChar()
    {
      if (textPos < textLen) textPos++;
      ch = textPos < textLen ? text[textPos] : '\0';
    }

    void NextToken()
    {
      while (Char.IsWhiteSpace(ch)) NextChar();
      TokenId t;
      int tokenPos = textPos;
      switch (ch)
      {
        case '!':
          NextChar();
          if (ch == '=')
          {
            NextChar();
            t = TokenId.ExclamationEqual;
          }
          else
          {
            t = TokenId.Exclamation;
          }
          break;
        case '%':
          NextChar();
          t = TokenId.Percent;
          break;
        case '&':
          NextChar();
          if (ch == '&')
          {
            NextChar();
            t = TokenId.DoubleAmphersand;
          }
          else
          {
            t = TokenId.Amphersand;
          }
          break;
        case '(':
          NextChar();
          t = TokenId.OpenParen;
          break;
        case ')':
          NextChar();
          t = TokenId.CloseParen;
          break;
        case '*':
          NextChar();
          t = TokenId.Asterisk;
          break;
        case '+':
          NextChar();
          t = TokenId.Plus;
          break;
        case ',':
          NextChar();
          t = TokenId.Comma;
          break;
        case '-':
          NextChar();
          t = TokenId.Minus;
          break;
        case '.':
          NextChar();
          t = TokenId.Dot;
          break;
        case '/':
          NextChar();
          t = TokenId.Slash;
          break;
        case ':':
          NextChar();
          t = TokenId.Colon;
          break;
        case '<':
          NextChar();
          if (ch == '=')
          {
            NextChar();
            t = TokenId.LessThanEqual;
          }
          else if (ch == '>')
          {
            NextChar();
            t = TokenId.LessGreater;
          }
          else
          {
            t = TokenId.LessThan;
          }
          break;
        case '=':
          NextChar();
          if (ch == '=')
          {
            NextChar();
            t = TokenId.DoubleEqual;
          }
          else
          {
            t = TokenId.Equal;
          }
          break;
        case '>':
          NextChar();
          if (ch == '=')
          {
            NextChar();
            t = TokenId.GreaterThanEqual;
          }
          else
          {
            t = TokenId.GreaterThan;
          }
          break;
        case '?':
          NextChar();
          t = TokenId.Question;
          break;
        case '[':
          NextChar();
          t = TokenId.OpenBracket;
          break;
        case ']':
          NextChar();
          t = TokenId.CloseBracket;
          break;
        case '|':
          NextChar();
          if (ch == '|')
          {
            NextChar();
            t = TokenId.DoubleBar;
          }
          else
          {
            t = TokenId.Bar;
          }
          break;
        case '"':
        case '\'':
          char quote = ch;
          do
          {
            NextChar();
            while (textPos < textLen && ch != quote) NextChar();
            if (textPos == textLen)
              throw ParseError(textPos, Res.UnterminatedStringLiteral);
            NextChar();
          } while (ch == quote);
          t = TokenId.StringLiteral;
          break;
        default:
          if (Char.IsLetter(ch) || ch == '@' || ch == '_')
          {
            do
            {
              NextChar();
            } while (Char.IsLetterOrDigit(ch) || ch == '_');
            t = TokenId.Identifier;
            break;
          }
          if (Char.IsDigit(ch))
          {
            t = TokenId.IntegerLiteral;
            do
            {
              NextChar();
            } while (Char.IsDigit(ch));
            if (ch == '.')
            {
              t = TokenId.RealLiteral;
              NextChar();
              ValidateDigit();
              do
              {
                NextChar();
              } while (Char.IsDigit(ch));
            }
            if (ch == 'E' || ch == 'e')
            {
              t = TokenId.RealLiteral;
              NextChar();
              if (ch == '+' || ch == '-') NextChar();
              ValidateDigit();
              do
              {
                NextChar();
              } while (Char.IsDigit(ch));
            }
            if (ch == 'F' || ch == 'f') NextChar();
            break;
          }
          if (textPos == textLen)
          {
            t = TokenId.End;
            break;
          }
          throw ParseError(textPos, Res.InvalidCharacter, ch);
      }
      token.id = t;
      token.text = text.Substring(tokenPos, textPos - tokenPos);
      token.pos = tokenPos;
    }

    bool TokenIdentifierIs(string id)
    {
      return token.id == TokenId.Identifier && String.Equals(id, token.text, StringComparison.OrdinalIgnoreCase);
    }

    string GetIdentifier()
    {
      ValidateToken(TokenId.Identifier, Res.IdentifierExpected);
      string id = token.text;
      if (id.Length > 1 && id[0] == '@') id = id.Substring(1);
      return id;
    }

    void ValidateDigit()
    {
      if (!Char.IsDigit(ch)) throw ParseError(textPos, Res.DigitExpected);
    }

    void ValidateToken(TokenId t, string errorMessage)
    {
      if (token.id != t) throw ParseError(errorMessage);
    }

    void ValidateToken(TokenId t)
    {
      if (token.id != t) throw ParseError(Res.SyntaxError);
    }

    Exception ParseError(string format, params object[] args)
    {
      return ParseError(token.pos, format, args);
    }

    Exception ParseError(int pos, string format, params object[] args)
    {
      return new ParseException(string.Format(System.Globalization.CultureInfo.CurrentCulture, format, args), pos);
    }

    static Dictionary<string, object> CreateKeywords()
    {
      Dictionary<string, object> d = new Dictionary<string, object>(StringComparer.OrdinalIgnoreCase);
      d.Add("true", trueLiteral);
      d.Add("false", falseLiteral);
      d.Add("null", nullLiteral);
      d.Add(keywordIt, keywordIt);
      d.Add(keywordIif, keywordIif);
      d.Add(keywordNew, keywordNew);
      foreach (Type type in predefinedTypes) d.Add(type.Name, type);
      return d;
    }
  }

  static class Res
  {
    public const string DuplicateIdentifier = "The identifier '{0}' was defined more than once";
    public const string ExpressionTypeMismatch = "Expression of type '{0}' expected";
    public const string ExpressionExpected = "Expression expected";
    public const string InvalidCharacterLiteral = "Character literal must contain exactly one character";
    public const string InvalidIntegerLiteral = "Invalid integer literal '{0}'";
    public const string InvalidRealLiteral = "Invalid real literal '{0}'";
    public const string UnknownIdentifier = "Unknown identifier '{0}'";
    public const string NoItInScope = "No 'it' is in scope";
    public const string IifRequiresThreeArgs = "The 'iif' function requires three arguments";
    public const string FirstExprMustBeBool = "The first expression must be of type 'Boolean'";
    public const string BothTypesConvertToOther = "Both of the types '{0}' and '{1}' convert to the other";
    public const string NeitherTypeConvertsToOther = "Neither of the types '{0}' and '{1}' converts to the other";
    public const string MissingAsClause = "Expression is missing an 'as' clause";
    public const string ArgsIncompatibleWithLambda = "Argument list incompatible with lambda expression";
    public const string TypeHasNoNullableForm = "Type '{0}' has no nullable form";
    public const string NoMatchingConstructor = "No matching constructor in type '{0}'";
    public const string AmbiguousConstructorInvocation = "Ambiguous invocation of '{0}' constructor";
    public const string CannotConvertValue = "A value of type '{0}' cannot be converted to type '{1}'";
    public const string NoApplicableMethod = "No applicable method '{0}' exists in type '{1}'";
    public const string MethodsAreInaccessible = "Methods on type '{0}' are not accessible";
    public const string MethodIsVoid = "Method '{0}' in type '{1}' does not return a value";
    public const string AmbiguousMethodInvocation = "Ambiguous invocation of method '{0}' in type '{1}'";
    public const string UnknownPropertyOrField = "No property or field '{0}' exists in type '{1}'";
    public const string NoApplicableAggregate = "No applicable aggregate method '{0}' exists";
    public const string CannotIndexMultiDimArray = "Indexing of multi-dimensional arrays is not supported";
    public const string InvalidIndex = "Array index must be an integer expression";
    public const string NoApplicableIndexer = "No applicable indexer exists in type '{0}'";
    public const string AmbiguousIndexerInvocation = "Ambiguous invocation of indexer in type '{0}'";
    public const string IncompatibleOperand = "Operator '{0}' incompatible with operand type '{1}'";
    public const string IncompatibleOperands = "Operator '{0}' incompatible with operand types '{1}' and '{2}'";
    public const string UnterminatedStringLiteral = "Unterminated string literal";
    public const string InvalidCharacter = "Syntax error '{0}'";
    public const string DigitExpected = "Digit expected";
    public const string SyntaxError = "Syntax error";
    public const string TokenExpected = "{0} expected";
    public const string ParseExceptionFormat = "{0} (at index {1})";
    public const string ColonExpected = "':' expected";
    public const string OpenParenExpected = "'(' expected";
    public const string CloseParenOrOperatorExpected = "')' or operator expected";
    public const string CloseParenOrCommaExpected = "')' or ',' expected";
    public const string DotOrOpenParenExpected = "'.' or '(' expected";
    public const string OpenBracketExpected = "'[' expected";
    public const string CloseBracketOrCommaExpected = "']' or ',' expected";
    public const string IdentifierExpected = "Identifier expected";
  }
}